//Cow Frisbee Team S:https://www.luogu.com.cn/problem/P2946

#include <iostream>

using namespace std;

const int N = 2010,mod = 1e8;

int g[N][N];
int a[N];

int n,m;

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)cin >> a[i];
	
	g[0][0] = 1;
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= m; j++)
		{
			g[i][j] = (g[i-1][j] + (g[i-1][((j-a[i]%m)%m+m)%m]))%mod;
		}
	}	
	cout << g[n][0] - 1 << endl;
	return 0;
}
